#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : MergeTwoBinaryTrees.py
# @Time    : 2020/9/23 10:32
# @Description:
from collections import deque


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        """
        Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the
        two trees are overlapped while the others are not.
        
        You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values
         up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
        
        Example 1:
            Input:
                Tree 1                     Tree 2
                      1                         2
                     / \                       / \
                    3   2                     1   3
                   /                           \   \
                  5                             4   7
        Output: 
            Merged tree:
                     3
                    / \
                   4   5
                  / \   \
                 5   4   7

        Note: The merging process must start from the root nodes of both trees.

        :param t1:
        :param t2:
        :return:
        """
        if not t1:
            return t2
        if not t2:
            return t1

        merged = TreeNode(t1.val + t2.val)
        merged.left = self.mergeTrees(t1.left, t2.left)
        merged.right = self.mergeTrees(t1.right, t2.right)
        return merged

    def mergeTrees2(self, t1: TreeNode, t2: TreeNode):
        if not t1:
            return t2
        if not t2:
            return t1

        merged = TreeNode(t1.val + t2.val)
        queue = deque([merged])
        queue1 = deque([t1])
        queue2 = deque([t2])

        while queue1 and queue2:
            node = queue.popleft()
            node1 = queue1.popleft()
            node2 = queue2.popleft()
            left1, right1 = node1.left, node1.right
            left2, right2 = node2.left, node2.right
            if left1 or left2:
                if left1 and left2:
                    left = TreeNode(left1.val + left2.val)
                    node.left = left
                    queue.append(left)
                    queue1.append(left1)
                    queue2.append(left2)
                elif left1:
                    node.left = left1
                elif left2:
                    node.left = left2

            if right1 or right2:
                if right1 and right2:
                    right = TreeNode(right1.val + right2.val)
                    node.right = right
                    queue.append(right)
                    queue1.append(right1)
                    queue2.append(right2)
                elif right1:
                    node.right = right1
                elif right2:
                    node.right = right2
        return merged


if __name__ == '__main__':
    S = Solution()
    t1 = TreeNode(1)
    t1.left = TreeNode(3)
    t1.right = TreeNode(2)
    t1.left.left = TreeNode(5)

    t2 = TreeNode(2)
    t2.left = TreeNode(1)
    t2.right = TreeNode(3)
    t2.left.right = TreeNode(4)
    t2.right.right = TreeNode(7)
    m1 = S.mergeTrees(t1, t2)
    m2 = S.mergeTrees2(t1, t2)
    print('done')
